# Leetcode123算法复杂度分析
# 时间复杂度：O(n)，其中n为价格数组长度。只需遍历三次数组。
# 空间复杂度：O(n)，需要两个长度为n的辅助数组。

import matplotlib.pyplot as plt
from alg import Solution
import numpy as np
import time

# 基础算法正确性检验
# 用例格式：(输入, 期望输出)
def check_correctness():
    so = Solution()
    test_cases = [
        ([1,2,3,4,5], 4),
        ([3,3,5,0,0,3,1,4], 6),
        ([1], 0),
        ([7,6,4,3,1], 0),
        ([1,2,4,2,5,7,2,4,9,0], 13),
        ([2,1,2,0,1], 2),
    ]
    for i, (prices, expected) in enumerate(test_cases):
        result = so.maxProfit(prices)
        print(f"用例{i+1}: 输入={prices}，期望输出={expected}，实际输出={result}", end=' ')
        assert result == expected, f"❌ 未通过: 输入={prices}，期望={expected}，实际={result}"
        print("✅ 通过")

class test_Leetcode123:
    so = Solution()

    lengths = [200, 400, 800, 1600, 3200, 6400, 12800]
    times = []

    def normalization(ref, base):
        # 使用最大值进行归一化，这样可以保持曲线的相对形状
        return [x/ref[0] * base[0] for x in ref]

    n = np.array(lengths)
    nlogn = n * np.log2(n)
    n2 = n ** 2

    for length in lengths:
        prices = np.random.randint(0, 1000, size=length).tolist()
        start_time = time.perf_counter()
        so.maxProfit(prices)
        end_time = time.perf_counter()
        times.append(end_time - start_time)
        print(f"长度为{length}的测试用例，运行时间为{end_time - start_time}秒")

    plt.plot(n, times, 'bo-',label = "Measured Time", linewidth = 2)
    plt.plot(n, normalization(n, times), 'm--', label = "O(n)", linewidth = 2)
    plt.plot(n, normalization(nlogn, times), 'g--', label = "O(nlogn)", linewidth = 2)
    plt.plot(n, normalization(n2, times), 'r--',label = "O(n^2)", linewidth = 2)

    plt.yscale('log')
    plt.xlabel('Length of input list')
    plt.ylabel('Run Times (seconds)')
    plt.title('Leetcode123 Performance Analysis')
    plt.grid(True)
    plt.legend()
    plt.tight_layout()
    plt.show()
    plt.savefig('Leetcode123.png')

if __name__ == "__main__":
    print("基础算法正确性检验：")
    check_correctness()
    print("\n开始性能分析：")
    test = test_Leetcode123()
